package leetcode;

public class IntegerReplacement {

	public static void main(String[] args) {
		IntegerReplacement object = new IntegerReplacement();
		object.integerReplacement(Integer.MAX_VALUE);
	}
	
	public int integerReplacement(int num) {
		if(num <= 0){
			return -1;
		}
		long n = num;
		if(n == 1) return 0;
		int res = 0;
		while(n > 1){
			if( (n & 1) == 0){
				n >>>= 1;
			}else{
				//思路不对：比如39
				//正确的应该是     39 -> 40 -> 20 -> 10 -> 5 -> 4 -> 2 -> 1
				//我这个会变为: 39 -> 38 -> 19 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1
				
				//40： 101000
				//38： 100110
				//应该选择最右边的 1 尽量靠左的，表示可以除二的次数多
				// 还要避免n + 1溢出
				int add = getRightOnePosition(n + 1);
				int minus = getRightOnePosition(n - 1);
				System.out.println(" add: " + add + " minus: " + minus);
				if(n > 7 && add > minus){
					n += 1;
				}else{
					n -= 1;
				}
			}
			res++;
		}
		System.out.println(res);
		return res;
	}
	
	/**
	 * @return 返回-1表示不包含1,最右边的一位表示1
	 */
	public int getRightOnePosition(long n){
		if(n == 0){
			return -1;
		}
		int res = 1;
		while(n > 0){
			if( (n & 1) == 1){
				return res;
			}else{
				n >>>= 1;
				res++;
			}
		}
		return res;
	}
}
